/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/single-number-ii
   @Language: C++
   @Datetime: 16-02-09 08:32
   */

// Method 1, statistics each bit count, Time 138ms
class Solution {
public:
	/**
	 * @param A : An integer array
	 * @return : An integer
	 * Tip: statistics each bit count
	 */
	int singleNumberII(vector<int> &A) {
		// write your code here
		int bit=0, ans=0, i, j;
		for(i=0; i<32; ++i){
			bit = 0;
			for(j=A.size(); j; )
				bit+=(A[--j]>>i)&1;
			ans |= (bit%3)<<i;
		}
		return ans;
	}
};

// Method 2, HashMap, Time 146ms
class Solution {
public:
	/**
	 * @param A : An integer array
	 * @return : An integer 
	 * Tip: Using hash map statistics each number appearence times
	 */
	int singleNumberII(vector<int> &A) {
		// write your code here
		unordered_map<int,int> hash;
		for(const auto &a:A)
			++hash[a];
		for(const auto &h:hash)
			if (h.second==1) return h.first;
		return 0;
	}
};

// Method 3, one and two, Time 117ms
class Solution {
public:
	/**
	 * @param A : An integer array
	 * @return : An integer 
	 * Tip: one contains all numbers which exists once,
	 *      two contains all numbers which exists twice.
	 * when a exists three times, set both one and two as clean.
	 */
	int singleNumberII(vector<int> &A) {
		// write your code here
		int one=0, two=0, i;
		for (i=A.size()-1; i>-1; --i){
			one = (one^A[i])&(~two);
			two = (two^A[i])&(~one);
		}
		return one;
	}
};
